Stekelenburg membuat penampilan pertama antarabangsa bersama pasukan kebangsaan Belanda pada 3 September 2004 menentang Liechtenstein, Belanda menang 3–0.

Beliau dipanggil oleh pengurus Marco van Basten untuk skuad Piala Dunia FIFA 2006 di Jerman tetapi tidak bermain sebarang perlawanan kerana Edwin van der Sar menjadi pilihan pertama.

Beliau dipanggil oleh pengurus van Basten untuk skuad UEFA Euro 2008. Beliau hanya bermain pada perlawanan terakhir kumpulan C kejohanan menentang Romania.

Pada September 2008, satu perlawanan persahabatan menentang Australia, Stekelenburg dibuang padang pada 44 minit perlawanan selepas melakukan faul ke atas pemain Joshua Kennedy. Stekelenburg merupakan penjaga gol pertama Belanda yang pernah dilayangkan kad merah.

Selepas Van der Sar bersara daripada pasukan kebangsaan, Stekelenburg menjadi pilihan pertama penjaga gol Belanda di bawah pengurus Bert van Marwijk. Stekelenburg termasuk dalam skuad Piala Dunia FIFA 2010 di Afrika Selatan.[5] Pada 27 Mei 2010, beliau termasuk dalam senarai akhir 23 pemain oleh jurulatih Van Marwijk ke Afrika Selatan. Beliau berjaya menampan dari sepakan terbaik oleh Kaká ketika Belanda menang 2-1 ke atas Brazil pada suku akhir. Beliau hanya dibolosi enam gol pada kejohanan dan terlepas ketika perlawanan akhir menentang Andrés Iniesta.

Stekelenburg bermain kesemua perlawanan peringkat kumpulan pada UEFA Euro 2012 dan Belanda menduduki tempat tercorot kumpulan. Pada 16 Oktober 2012 merupakan penampilan antarabangsa terakhir untuknya. Beliau kemudian tidak termasuk dalam senarai akhir Piala Dunia FIFA 2014 di Brazil.

Statistik